/*
# File    :   segment_tree.c
# ref     :   https://www.cnblogs.com/xiaoyao24256/p/6590885.html
# Date    :   Sat, May 25, 2019  5:44:39 PM
*/

#include<stdio.h>
/*i表示当前递归编号,l,r分别表示当前点的左右区间*/
/*Tree数组是存储线段树的数组*/
void Build(int i, int l, int r) {
    /*
     *怎么判断是叶子结点？怎么递归左右子树？现在，往上翻，看看线段树的性质。
     至于叶子节点的判断,我们也可以利用线段树的性质。叶子结点没有子节点，那么它的左右区间必定相同(即一个点而不是一条线段)，否则可以继续向下递归。

     　　另外，线段树是一棵满二叉树，所以满足满二叉树一个性质:父亲节点编号为a,那么左子树编号为2*a,右子树编号为2*a+1
     * */

    if(l == r) {
        scanf("%d", Tree[i]);
        return;
    }
    int Mid = (l + r) / 2;
    Build(i * 2, l, Mid);
    Build(i * 2, Mid + 1, r);
    PushUp(i) /*这是什么?往后看*/      
}


/*线段树中的修改操作一定只能使用特别的操作来完成，千万不要自以为是的写一些似乎是对的代码

  　　那么怎么做呢?我们来分析一下。

  　　如果要找到这个点A，我们必须要递归左右子树来寻找。上面介绍了递归的方法，大家是否已经发现了这样的递归很像某一种算法?没错，就是分治(如果要理解成二分也没有问题)，那么问题就很显然了，每次都二分，如果要寻找的点A在当前区间的中点，即(l+r)/2之前，就递归左子树，否则递归右子树。*/

/*i为当前编号,L,R为左右区间,A为修改点的编号,B为修改的值*/
void Update_Single(int i, int L, int R, int A, int B) {
    if(L == R) {
        /*如果找到了,修改值*/
        Tree[i] == B;
        return;
    }
    int Mid = (L + R) / 2;
    if(A <= Mid) Update_Single(i * 2, L, Mid, A, B); /*递归左子树*/
    else Update_Single(i * 2 + 1, Mid + 1, R, A, B); /*递归右子树*/
    PushUp(i); /*这是什么?往后看*/
}


/*区间求和其实非常简单，我们只需要查询给定的区间，然后找到这个区间里面的所有叶子结点，把叶子结点的权值加起来，得到的结果就是我们所需要的区间和。那么要PushUp干嘛呢?PushUp简化了这个过程。在原本的操作里，最差的情况是要递归一直到叶子结点，多么令人心痛的浪费时间！然而我们用PushUp预处理之后，就变成了前缀和问题，求和不就是小菜一碟吗？*/
/*i 为当前编号, L, R为查询区间*/
int Quary_Total(int i, int L, int R, int l, int r) {
    if(l >= L && r <= R) return Tree[i]; /*如果在区间内*/
    int Mid = (L + R) / 2, Cnt = 0; /*初始化*/
    if(L <= Mid) Cnt += Quary_Total(i * 2, L, R, l, Mid); /*递归左子树*/
    if(R > Mid)  Cnt += Quary_Total(i * 2 + 1, L, R, Mid + 1, r); /*递归右子树*/
    return Cnt;
}


/*其实区间最值完全可以放在区间和里面讲的，因为写法几乎一样，唯一不同的是PushUp的方式以及判断的方式。因为在PushUp的时候预处理每一棵子树的最值，所以真正处理区间时只要把上面一层扫过去就可以了。*/
int Quary_RMQ(int i, int L, int R, int l, int r) {
    if(l >= L && r <= R) return Tree[i];
    int Mid = (L + R) / 2, Cnt = 0;
    int A, B;
    A = Quary_RMQ(i * 2, L, R, l, Mid);
    B = Quary_RMQ(i * 2 + 1, L, R, Mid + 1, R);
    return Max(A, B); /*返回最大值*/
}

